matrix=[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
# matrix=[[-5]]

target=20
def findNumberIn2DArray(matrix, target: int) -> bool:
    matrixRow=len(matrix)
    matrixCol=len(matrix[0])

    row_l,row_r=0,matrixRow-1
    while row_l<row_r:
        mid=int((row_l+row_r+1)/2)
        if matrix[mid][0]<target:
            row_l=mid
        if matrix[mid][0]==target:
            return True
        if matrix[mid][0]>target:
            row_r=mid-1

    col_l,col_r=0,matrixCol-1
    while col_l<col_r:
        mid=int((col_l+col_r+1)/2)
        if matrix[0][mid]<target:
            col_l=mid
        if matrix[0][mid]==target:
            return True
        if matrix[0][mid]>target:
            col_r=mid-1

    for i in range(0,row_l+1):
        for j in range(0,col_l+1):
            if matrix[i][j]==target:
                return True
    return False


def findNumberIn2DArray1(matrix, target: int) -> bool:
    i=len(matrix)-1
    j=0
    while i>=0 and i<len(matrix) and j>=0 and j<len(matrix[0]):
        flag=matrix[i][j]
        if flag==target:
            return True
        if flag<target:
            j+=1
        if flag>target:
            i-=1
    return False


print(findNumberIn2DArray1(matrix,target))